Case study:

1. Searching

Pool: 
1	5	7	11	15
target: 
12

- Linear search

Time complexity: O(n) where n is the size of the array
Application#1: SearchingApp.java

- Binary search

We perform binary search only if the pool is sorted 
target: 12				middle
					left
				right	
idxes:  0	1	2	3	4
values: 1	5	7	11	15

boolean found = false;

int middle = left + (right - left) / 2;
As long as I haven't found the value yet and left <= right
if(pool[middle] == target) {
	found = true;
} else if(pool[middle] < target) {
	left = middle + 1;
} else {
	right = middle - 1;
}

Time complexity: O(log2(n)) where n is the size of the array

Is it a good idea to sort and then do binary search?
1. Sort the elements: O(n log2(n))
2. Do binary search: O(log2(n))
--------------------------------
Overall time complexity: O(n log2(n)) which is worse than linear search


2. Sorting

arr
5	1	10	2

1	5	2	10
1	2	5	10
Bubble sort

Selection sort: 
5	1	10	2

For every position, select the value that should occupy that position in the sroted array
1	5	10	2
1	2	10	5
1	2	5	10

Consider a simpler version of the problem?
I wish I could do it for the first position (Wishful thinking)
Simpler version of the problem: let the smallest value occupy the first position in the array

for(int idx = 0; idx < arr.length - 1; idx++) {
int idxMin = idx;

for(int scan = idx + 1; scan < arr.length; scan++) {
	if(arr[scan] < arr[idxMin]) { idxMin = scan; }
}

swap(arr, idx, idxMin);
}


n - 1 + n - 2 + ... + 1 = n ( n - 1) / 2 = O(n^2)





















